import java.util.*;

/**
 * Created by L.jp
 * Description:给定一个长度为 n 的可能有重复值的数组，找出其中不去重的最小的 k 个数。
 * 例如数组元素是4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4(任意顺序皆可)
 * User: 86189
 * Date: 2021-12-27
 * Time: 23:16
 */
//建立一个容量为k的大根堆的优先队列。
// 遍历一遍元素，如果队列大小<k,就直接入队，否则，让当前元素与队顶元素相比，如果队顶元素大，则出队，将当前元素入队

//大根堆(前 K 小)
// 小根堆（前 K 大)
    //本题是求前 K 小，因此用一个容量为 K 的大根堆，每次 poll 出最大的数，那堆中保留的就是前 K 小啦
public class TopK {
    public static  ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        //法一:大根堆
        ArrayList<Integer> topmin = new ArrayList<>();
        if(input==null || k==0 || k>input.length){
            return  topmin;
        }
        //默认是小根堆，那么我们需要建立大根堆,按照从大到小的顺序的大根堆，返回值是o2-o1才是大根堆
        PriorityQueue<Integer> p=new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2-o1;
            }
        });
        //或者直接使用参数构造大根堆
        /*返回一个比较器，它在实现Comparable接口的对象集合上强加自然顺序的反向。 （自然排序是由对象自己的compareTo方法强加的排序。）这为排序（或维护）以反向自然顺序实现Comparable接口的对象的集合（或数组）提供了一个简单的习惯用法。 例如，假设a是一个字符串数组。 然后：
        Arrays.sort(a, Collections.reverseOrder());

        以逆字典（字母）顺序对数组进行排序。
        返回的比较器是可序列化的。
        返回值：
        一个比较器，它对实现Comparable接口的对象集合强加自然顺序的反向*/
        //实际就自然排序就是从小到大，用了这个reverseOrder后就是反向排序了，变成了从大到小
        //构造了一个具有给定容量的有着比较顺序规则的大根堆
        //PriorityQueue<Integer> q=new PriorityQueue<>(k, Collections.reverseOrder());
        for(int i=0;i<input.length;i++){
            //大根堆的存放的数还没到k个时
            if(i<k){
                //入堆
                p.offer(input[i]);
            }else{
                //需要找到前k个最小的，如果当前遍历到的数比堆顶元素小，那么就要弹出堆顶元素，加入当前数字元素
                if(input[i]<p.peek()){
                    p.poll();
                    p.offer(input[i]);
                }
            }
        }
        //需要将前k个堆元素加入到结果集
        for(int i=0;i<k;i++){
            topmin.add(p.poll());
        }
        return topmin;


        //法二：快排
        

    }

    public static void main(String[] args) {
        int[] input={1,2,3,4,5,6,7,8};
        System.out.println(GetLeastNumbers_Solution(input, 4));

    }
}
